Network packet routers use buffer management techniques to share limited buffer space between various incoming data ports and classes of data packets. Typically, the packets are divided into cells that are managed by a set of queues. Packets from multiple ports are en-queued to multiple queues based on their classified priority and de-queued based on available bandwidth of the shared output port(s). Often the available output bandwidth is less than in aggregate input bandwidth and packets must be dropped because there is limited shared buffer memory. If there is efficient buffer management of the shared buffer memory, overall loss performance, as well as fairness between ports, can be improved. However, there are many restrictions on implementing the buffer management scheme. The hardware implementing the management must operate at the rate of the incoming packets, and this rate approaches the maximum rate that can be realized using current memory technology.
Prior work has shown that overall fairness of queue management is maximized by dropping packets from the head of the queues. This process, called a “head-drop” process, drops packets from the head of the queue when buffer space is low, so that new packets may be inserted at the tail of the queue. The use of a head-drop process in parallel with a de-queue process achieves superior fairness among the queues. However, the parallel operation of the head-drop and de-queue operations requires that the data structure implementing the queues be able to support parallel access from the two processes. Thus, the memory implementing the queue structure needs a higher bandwidth than is required by the de-queue process alone to support parallel operation. The use of this higher bandwidth to support the parallel head-drop and de-queue operations is inefficient. Furthermore, head-drop mechanisms are often unable to limit queue length under worst case traffic patterns, and require an additional process in order to ensure correct functionality. This additional process is typical a “tail drop” process, where packets are dropped from the tail of the queue. Alternately, instead of head-drop, a tail-drop operation based on thresholds may be implemented during the en-queue process. In these cases, the increased bandwidth requirements do not occur. However, tail-drop operations are not as efficient as head-drop operations.